from typing import List

class SegmentTree:
    def __init__(self, elements):
        self.size = len(elements)
        n = self.tableSize(self.size) + 1
        self.n = n
        self.tree = [[0, 0]] * (n * 2)
        self.lazy = [0] * (n * 2)
        for i, e in enumerate(elements):
            self.tree[i + n] = [e, 1]
        i = n - 1
        while i > 0:
            self.tree[i] = [self.tree[i*2][0] + self.tree[i*2+1]
                            [0], self.tree[i*2][1] + self.tree[i*2+1][1]]
            i -= 1
        print(self.tree)
        print(self.size)
        print(self.n)

    def tableSize(self, n):
        a = n
        a |= a >> 1
        a |= a >> 2
        a |= a >> 4
        a |= a >> 8
        a |= a >> 16
        return a

    # 把区间 [i, j) 范围内的所有值都 merge e
    def mergeRange(self, i, j, e):
        self._mergeRange(1, 0, self.n, i, j, e)

    def _mergeRange(self, pos, left, right, i, j, e):
        if right <= i or j <= left:
            return  # 啥也不做
        if i <= left and right <= j:
            self.lazy[pos] += e
            # 往上更新和
            aug = self.tree[pos][1] * e
            i = pos // 2
            while i > 0:
                self.tree[i][0] += aug
                i //= 2
            return
        mid = (left + right) // 2
        self._mergeRange(pos*2, left, mid, i, j, e)
        self._mergeRange(pos*2+1, mid, right, i, j, e)

    def merge(self, i, e):
        self._mergeRange(1, 0, self.n, i, i+1, e)

    # 注意，按照不成文的约定，包含 i 但不包含 j
    def query(self, i, j):
        return self._query(1, 0, self.n, i, j)

    def _query(self, pos, left, right, i, j):
        if right <= i or j <= left:
            return 0
        if i <= left and right <= j:
            # 往上更新和
            self._pushDown(pos)
            return self.tree[pos][0]
        self._pushDown(pos)
        mid = (left + right) // 2
        return self._query(pos*2, left, mid, i, j) + self._query(pos*2+1, mid, right, i, j)

    # 向下把 lazy 传递一层。注意，这里的 i 是 tree 中的索引
    def _pushDown(self, i):
        clazy = self.lazy[i]
        if clazy <= 0:
            return
        if i > self.n:
            self.tree[i][0] += clazy
        else:
            self.tree[i][0] += (clazy * (self.tree[i][1]))
            self.lazy[i*2] += clazy
            self.lazy[i*2+1] += clazy
        self.lazy[i] = 0

class Solution:
    def __init__(self):
        self.stId = -1
        self.orderedMembers = []
        self.memberIdToNode = dict()
        self.graph = dict()
        self.st = SegmentTree([0])

    def bonus(self, n: int, leadership: List[List[int]], operations: List[List[int]]) -> List[int]:
        self.orderedMembers = [None] * (n + 1)
        self.leaderShipToGraph(leadership)
        print(self.graph)
        self.codeGraph(1, 0)
        print("Orderred Member Nodes:", self.orderedMembers)
        print("MemberId to Node:", self.memberIdToNode)
        self.st = SegmentTree([0]*n)

        result = []
        for op in operations:
            if op[0] == 1:
                self.coin1(op[1], op[2])
            elif op[0] == 2:
                self.coinGroup(op[1], op[2])
            elif op[0] == 3:
                result.append(self.query(op[1]) % 1000000007)
        return result

    def leaderShipToGraph(self, leadership: List[List[int]]):
        graph = dict()
        for [leader, member] in leadership:
            if leader not in graph:
                graph[leader] = []
            graph[leader].append(member)
        self.graph = graph

    def codeGraph(self, i, p):
        self.stId += 1
        currId = self.stId
        self.orderedMembers[currId] = {"member": i, "curr": currId}
        self.memberIdToNode[i] = self.orderedMembers[currId]
        if i in self.graph:
            for j in self.graph[i]:
                self.codeGraph(j, i)
        self.orderedMembers[currId]["end"] = self.stId + 1

    def coin1(self, memberId, coin):
        node = self.memberIdToNode[memberId]
        i = node["curr"]
        self.st.merge(i, coin)

    def coinGroup(self, memberId, coin):
        node = self.memberIdToNode[memberId]
        i, end = node["curr"], node['end']
        self.st.mergeRange(i, end, coin)

    def query(self, memberId):
        print(self.st.tree)
        node = self.memberIdToNode[memberId]
        i, end = node["curr"], node['end']
        return self.st.query(i, end)


solu = Solution()
n = 408
ls = [[1, 283], [1, 52], [1, 273], [1, 217], [1, 136], [1, 211], [1, 179], [283, 293], [283, 292], [283, 227], [283, 54], [283, 404], [283, 378], [283, 243], [283, 270], [283, 46], [283, 300], [52, 376], [52, 267], [52, 71], [52, 406], [273, 9], [273, 148], [273, 51], [273, 102], [217, 110], [217, 370], [217, 125], [217, 357], [136, 360], [136, 260], [136, 196], [136, 228], [136, 103], [136, 347], [136, 384], [211, 25], [179, 3], [179, 140], [179, 56], [179, 263], [179, 231], [293, 326], [293, 121], [293, 116], [293, 21], [293, 262], [293, 369], [293, 183], [292, 75], [292, 303], [292, 330], [227, 397], [227, 35], [227, 279], [227, 345], [227, 139], [227, 391], [227, 266], [54, 16], [404, 214], [404, 184], [404, 68], [404, 27], [378, 192], [378, 87], [378, 39], [378, 386], [378, 259], [243, 94], [243, 112], [243, 99], [243, 182], [243, 29], [243, 197], [270, 23], [270, 181], [270, 297], [46, 351], [46, 362], [46, 22], [46, 61], [300, 408], [376, 332], [267, 349], [267, 80], [267, 367], [267, 226], [71, 72], [71, 389], [71, 163], [71, 100], [71, 107], [71, 92], [71, 85], [406, 353], [406, 199], [406, 257], [406, 242], [406, 305], [406, 159], [406, 77], [9, 309], [148, 401], [148, 65], [148, 218], [148, 342], [148, 331], [148, 339], [51, 290], [51, 150], [51, 60], [51, 137], [51, 160], [51, 252], [51, 364], [51, 335], [51, 343], [51, 304], [102, 180], [102, 138], [110, 74], [110, 171], [110, 390], [110, 352], [110, 37], [370, 377], [370, 358], [370, 36], [370, 272], [125, 66], [125, 301], [125, 67], [125, 239], [125, 175], [357, 12], [357, 106], [357, 282], [357, 240], [360, 144], [360, 393], [360, 317], [360, 195], [260, 264], [260, 13], [260, 281], [260, 400], [260, 212], [260, 365], [260, 402], [260, 63], [260, 255], [196, 193], [196, 338], [228, 399], [228, 202], [228, 313], [228, 392], [228, 208], [228, 38], [228, 31], [103, 203], [103, 320], [103, 254], [103, 275], [103, 34], [347, 149], [347, 222], [347, 114], [347, 157], [347, 325], [347, 6], [347, 154], [347, 250], [347, 350], [384, 93], [384, 123], [384, 374], [384, 50], [25, 285], [25, 20], [25, 288], [25, 251], [25, 185], [25, 289], [3, 241], [3, 258], [3, 43], [140, 58], [140, 329], [140, 45], [140, 287], [140, 132], [140, 170], [140, 355], [140, 311], [140, 47], [140, 168], [56, 321], [56, 388], [56, 32], [56, 302], [56, 190], [56, 48], [56, 11], [263, 96], [263, 30], [263, 24], [263, 26], [231, 229], [231, 164], [231, 128], [231, 295], [231, 230], [231, 396], [231, 81], [231, 244], [231, 276], [231, 141], [326, 134], [326, 161], [326, 97], [326, 286], [326, 88], [326, 221], [326, 405], [326, 8], [326, 156], [121, 113], [121, 15], [121, 348], [121, 104], [121, 398], [121, 91], [121, 40], [121, 64], [121, 318], [121, 111], [116, 271], [21, 83], [21, 55], [262, 368], [262, 336], [262, 249], [262, 129], [262, 145], [262, 337], [262, 234], [262, 79], [369, 90], [369, 122], [369, 395], [369, 108], [369, 341], [369, 334], [369, 316], [369, 69], [369, 278], [183, 151], [183, 315], [183, 17], [183, 178], [183, 274], [183, 269], [75, 200], [75, 131], [75, 126], [75, 19], [75, 359], [75, 70], [75, 133], [75, 117], [75, 33], [75, 206], [303, 223], [303, 324], [303, 101], [303, 314], [303, 135], [303, 146], [330, 191], [330, 194], [330, 253], [330, 307], [330, 225], [330, 299], [330, 382], [330, 82], [397, 167], [397, 2], [397, 308], [397, 246], [397, 245], [397, 265], [35, 261], [35, 328], [35, 224], [35, 296], [35, 340], [35, 186], [35, 280], [279, 210], [279, 4], [279, 268], [279, 173], [279, 284], [279, 247], [279, 119], [279, 89], [279, 205], [345, 10], [345, 124], [345, 366], [345, 7], [345, 98], [345, 209], [345, 394], [345, 385], [345, 188], [345, 166], [139, 153], [139, 327], [139, 127], [139, 155], [139, 312], [391, 235], [391, 76], [391, 381], [266, 219], [266, 5], [266, 361], [266, 120], [266, 344], [266, 105], [266, 371], [266, 165], [266, 323], [16, 59], [16, 237], [16, 291], [16, 109], [214, 383], [214, 142], [214, 220], [214, 215], [184, 78], [184, 238], [184, 57], [68, 204], [27, 356], [27, 322], [27, 62], [27, 162], [27, 407], [27, 14], [27, 152], [27, 86], [27, 84], [27, 95], [192, 42], [87, 115], [87, 403], [87, 118], [87, 189], [87, 28], [87, 277], [87, 147], [87, 49], [39, 73], [386, 213], [386, 387], [386, 306], [386, 346], [386, 143], [386, 363], [386, 41], [386, 373], [259, 216], [259, 372], [259, 169], [259, 248], [259, 354], [259, 53], [259, 44], [259, 380], [259, 256], [94, 333], [94, 172], [94, 298], [94, 18], [94, 232], [94, 158], [94, 207], [94, 236], [112, 310], [112, 130], [112, 319], [112, 174], [99, 177], [99, 233], [99, 187], [99, 198], [99, 375], [99, 201], [99, 176], [99, 294], [99, 379]]
ops = [ [1, 201, 26], [1, 114, 22], [2, 366, 42], [3, 1],
        [2, 116, 22], [3, 1]]
# n = 6
# ls = [[1, 2], [1, 6], [2, 3], [2, 5], [1, 4]]
# ops = [[1, 1, 500], [2, 2, 50], [3, 1], [2, 6, 15], [3, 1]]
print(solu.bonus(n, ls,  ops))
